/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	src/tree.c
 * @brief 
 *      Tree module, A basic datastruct module.
 *      Memory-free operations, generic frame of tree datastructs
 *      -1. search tree
 *	      -RB-tree, splay-tree, SBT-tree, treap,
 *	      -radix-tree, B+-tree, merkle-tree
 *      -2. space partition tree
 *	      -D-tree, R-tree, Octree, Quad-tree
 * 
 * @see		dlib
 * @history
 *		version 0.1.0, spark init tree module with rbtree 
 *		version 0.2.0, spark add splay tree and sbt tree
 *		version 0.3.0, spark add radix tree
 *
 */

#include <stdlib.h>
#include <string.h>
#include "tree.h"

#ifndef _DLIB_NO_RBTREE
/**
 * Red-Black tree model
 * a binary search tree model
 */
static inline void _rb_rotate_left(rbtree_head_t *head, rbtree_node_t *node);
static inline void _rb_rotate_right(rbtree_head_t *head, rbtree_node_t *node);
static inline void _rb_insert_fixup(rbtree_head_t *head, rbtree_node_t *node);
static inline void _rb_delete_fixup(rbtree_head_t *head, rbtree_node_t *node);
static rbtree_node_t *_rb_find(rbtree_head_t *head, rbtree_node_t *node,
			       rb_search_t cmd, void *key);
static void _rb_inorder(rbtree_node_t *node, rb_walker_fn walker, void *arg);
static void _rb_postorder(rbtree_node_t *node, rb_walker_fn walker, void *arg);
static void _rb_preorder(rbtree_node_t *node, rb_walker_fn walker, void *arg);

/** rb_leaf: global node rb_leaf */
rbtree_node_t rb_leaf = {
	&rb_leaf, /* .left */
	&rb_leaf, /* .right */
	&rb_leaf, /* .parent */
	RB_BLACK, /* .color */
#ifdef _DLIB_RBTREE_SIZE
	0, /* .size */
#endif
};

static inline void _rb_rotate_left(rbtree_head_t *head, rbtree_node_t *node)
{
	rbtree_node_t *temp;

	temp = RB_RIGHT(node);
	RB_RIGHT(node) = RB_LEFT(temp);
	if (RB_LEFT(temp) != &rb_leaf) {
		RB_PARENT(RB_LEFT(temp)) = node;
	}

	RB_PARENT(temp) = RB_PARENT(node);

	if (RB_PARENT(node) == &rb_leaf) {
		RB_ROOT(head) = temp;
	} else {
		if (node == RB_LEFT(RB_PARENT(node))) {
			RB_LEFT(RB_PARENT (node)) = temp;
		} else {
			RB_RIGHT(RB_PARENT(node)) = temp;
		}
	}

	RB_LEFT(temp) = node;
	RB_PARENT(node) = temp;

#ifdef _DLIB_RBTREE_SIZE
	RB_SIZE(temp) = RB_SIZE(node);
	RB_SIZE(node) = RB_SIZE(RB_LEFT(node)) + RB_SIZE(RB_RIGHT(node)) + 1;
#endif
	return;
}

static inline void _rb_rotate_right(rbtree_head_t *head, rbtree_node_t *node)
{
	rbtree_node_t *temp;

	temp = RB_LEFT(node);
	RB_LEFT(node) = RB_RIGHT(temp);
	if (RB_RIGHT(temp) != &rb_leaf) {
		RB_PARENT(RB_RIGHT(temp)) = node;
	}

	RB_PARENT(temp) = RB_PARENT(node);

	if (RB_PARENT(node) == &rb_leaf) {
		RB_ROOT(head) = temp;
	} else {
		if (node == RB_RIGHT(RB_PARENT(node))) {
			RB_RIGHT(RB_PARENT(node)) = temp;
		} else {
			RB_LEFT(RB_PARENT(node)) = temp;
		}
	}

	RB_RIGHT(temp) = node;
	RB_PARENT(node) = temp;

#ifdef _DLIB_RBTREE_SIZE
	RB_SIZE(temp) = RB_SIZE(node);
	RB_SIZE(node) = RB_SIZE(RB_LEFT(node)) + RB_SIZE(RB_RIGHT(node)) + 1;
#endif
	return;
}

static inline void _rb_insert_fixup(rbtree_head_t *head, rbtree_node_t *node)
{
	rbtree_node_t *uncle;

	while (RB_IS_RED(RB_PARENT(node))) {
		if (RB_PARENT(node) == RB_LEFT(RB_PARENT(RB_PARENT(node)))) {
			uncle = RB_RIGHT(RB_PARENT(RB_PARENT(node)));
			if (RB_IS_RED(uncle)) {
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_BLACK(uncle);
				RB_SET_RED(RB_PARENT(RB_PARENT(node)));
				node = RB_PARENT(RB_PARENT(node));
			} else {
				if (node == RB_RIGHT(RB_PARENT(node))) {
					node = RB_PARENT(node);
					_rb_rotate_left(head, node);
				}
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_RED(RB_PARENT(RB_PARENT(node)));
				_rb_rotate_right(head,
						 RB_PARENT(RB_PARENT(node)));
			}
		} else {
			uncle = RB_LEFT(RB_PARENT(RB_PARENT(node)));
			if (RB_IS_RED(uncle)) {
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_BLACK(uncle);
				RB_SET_RED(RB_PARENT(RB_PARENT(node)));
				node = RB_PARENT(RB_PARENT(node));
			} else {
				if (node == RB_LEFT(RB_PARENT(node))) {
					node = RB_PARENT(node);
					_rb_rotate_right(head, node);
				}
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_RED(RB_PARENT(RB_PARENT(node)));
				_rb_rotate_left(head,
						RB_PARENT(RB_PARENT(node)));
			}
		}
	}

	RB_SET_BLACK(RB_ROOT(head));
	return;
}

static inline void _rb_delete_fixup(rbtree_head_t *head, rbtree_node_t *node)
{
	rbtree_node_t *sibling;

	while (node != RB_ROOT(head) && RB_IS_BLACK(node)) {
		if (node == RB_LEFT(RB_PARENT(node))) {
			sibling = RB_RIGHT(RB_PARENT(node));
			if (RB_IS_RED(sibling)) {
				RB_SET_BLACK(sibling);
				RB_SET_RED(RB_PARENT(node));
				_rb_rotate_left(head, RB_PARENT(node));
				sibling = RB_RIGHT(RB_PARENT(node));
			}

			if (RB_IS_BLACK(RB_LEFT(sibling)) &&
			    RB_IS_BLACK(RB_RIGHT(sibling))) {
				RB_SET_RED(sibling);
				node = RB_PARENT(node);
			} else {
				if (RB_IS_BLACK(RB_RIGHT(sibling))) {
					RB_SET_BLACK(RB_LEFT(sibling));
					RB_SET_RED(sibling);
					_rb_rotate_right(head, sibling);
					sibling = RB_RIGHT(RB_PARENT(node));
				}
				RB_COLOR(sibling) = RB_COLOR(RB_PARENT(node));
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_BLACK(RB_RIGHT(sibling));
				_rb_rotate_left(head, RB_PARENT(node));
				node = RB_ROOT(head);
			}
		} else {
			sibling = RB_LEFT(RB_PARENT(node));
			if (RB_IS_RED(sibling)) {
				RB_SET_BLACK(sibling);
				RB_SET_RED(RB_PARENT(node));
				_rb_rotate_right(head, RB_PARENT(node));
				sibling = RB_LEFT(RB_PARENT(node));
			}

			if (RB_IS_BLACK(RB_RIGHT(sibling)) &&
			    RB_IS_BLACK(RB_LEFT(sibling))) {
				RB_SET_RED(sibling);
				node = RB_PARENT(node);
			} else {
				if (RB_IS_BLACK(RB_LEFT(sibling))) {
					RB_SET_BLACK(RB_RIGHT(sibling));
					RB_SET_RED(sibling);
					_rb_rotate_left(head, sibling);
					sibling = RB_LEFT(RB_PARENT(node));
				}
				RB_COLOR(sibling) = RB_COLOR(RB_PARENT(node));
				RB_SET_BLACK(RB_PARENT(node));
				RB_SET_BLACK(RB_LEFT(sibling));
				_rb_rotate_right(head, RB_PARENT(node));
				node = RB_ROOT(head);
			}
		}
	} /* while */

	RB_SET_BLACK(node);
	return;
}

static rbtree_node_t *_rb_find(rbtree_head_t *head, rbtree_node_t *node,
			       rb_search_t cmd, void *key)
{
	int cmp;
	rbtree_node_t *ret = NULL;
	rbtree_node_t *cur;
	rbtree_node_t *stop;

	switch (cmd) {
	case RB_SEARCH_EQ: /* find exact */
		cmp = (*RB_COMPARE(head))
			(key, (void *)((long)node - head->key_space));
		while (node != &rb_leaf && cmp != 0) {
			if (cmp < 0) {
				node = RB_LEFT(node);
			} else {
				node = RB_RIGHT(node);
			}
			if (node != &rb_leaf) {
				cmp = (*RB_COMPARE(head))
					(key, (void *)((long)node - head->key_space));
			}
		}

		if (node != &rb_leaf)
			ret = node;

		break;
	case RB_SEARCH_LE: /* find litte-equal */
		cur = rb_maximum(node);
		stop = rb_minimum(node);
		cmp = (*RB_COMPARE(head))(key, (void *)((long)cur - head->key_space));
		while (cur != stop && cmp < 0) {
			cur = rb_predecessor(cur);
			cmp = (*RB_COMPARE(head))
				(key, (void *)((long)cur - head->key_space));
		}

		if (cmp >= 0)
			ret = cur;

		break;
	case RB_SEARCH_GE: /* find great-equal */
		cur = rb_minimum(node);
		stop = rb_maximum(node);
		cmp = (*RB_COMPARE(head))(key, (void *)((long)cur - head->key_space));
		while (cur != stop && cmp > 0) {
			cur = rb_successor(cur);
			cmp = (*RB_COMPARE(head))
				(key, (void *)((long)cur - head->key_space));
		}

		if (cmp <= 0)
			ret = cur;
		break;
	default:
		break;
	}

	return ret;
}

static void _rb_inorder(rbtree_node_t *node, rb_walker_fn walker, void *arg)
{
	if (node != &rb_leaf) {
		_rb_inorder(RB_LEFT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_rb_inorder(RB_RIGHT(node), walker, arg);
	}

	return;
}

static void _rb_postorder(rbtree_node_t *node, rb_walker_fn walker, void *arg)
{
	if (node != &rb_leaf) {
		_rb_postorder(RB_LEFT(node), walker, arg);
		_rb_postorder(RB_RIGHT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
	}

	return;
}

static void _rb_preorder(rbtree_node_t *node, rb_walker_fn walker, void *arg)
{
	if (node != &rb_leaf) {
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_rb_preorder(RB_LEFT(node), walker, arg);
		_rb_preorder(RB_RIGHT(node), walker, arg);
	}

	return;
}

int rb_init(rbtree_head_t *head, rb_compare_fn compare_fn,
		long key_space, long value_space)
{
	if (head == NULL || compare_fn == NULL || key_space == 0)
		return -1;

	INIT_RB_HEAD(head, compare_fn, key_space, value_space);

	return 0;
}

void rb_exit(rbtree_head_t *head, rb_walker_fn rb_free_node, void *arg)
{
	if (head == NULL) return;

	_rb_postorder(RB_ROOT(head), rb_free_node, arg);

	return;
}

rbtree_node_t *rb_minimum(rbtree_node_t *node)
{
	rbtree_node_t *ret = NULL;

	if (node == NULL)
		return NULL;

	ret = node;

	while (RB_LEFT(ret) != &rb_leaf) {
		ret = RB_LEFT(ret);
	}

	return ret;
}

rbtree_node_t *rb_maximum(rbtree_node_t *node)
{
	rbtree_node_t *ret = NULL;

	if (node == NULL)
		return ret;

	ret = node;

	while (RB_RIGHT(ret) != &rb_leaf) {
		ret = RB_RIGHT(ret);
	}

	return ret;
}

rbtree_node_t *rb_predecessor(rbtree_node_t *node)
{
	rbtree_node_t *ret;
	rbtree_node_t *temp;

	if (node == NULL)
		return NULL;

	ret = RB_LEFT(node);

	if (ret != &rb_leaf) {
		return rb_maximum(ret);
	}

	ret = RB_PARENT(node);
	temp = node;
	while (ret != &rb_leaf && temp == RB_LEFT(ret)) {
		temp = ret;
		ret = RB_PARENT(ret);
	}

	return ret;
}

rbtree_node_t *rb_successor(rbtree_node_t *node)
{
	rbtree_node_t *ret;
	rbtree_node_t *temp;

	if (node == NULL)
		return NULL;

	ret = RB_RIGHT(node);

	if (ret != &rb_leaf) {
		return rb_minimum(ret);
	}

	ret = RB_PARENT(node);
	temp = node;
	while (ret != &rb_leaf && temp == RB_RIGHT(ret)) {
		temp = ret;
		ret = RB_PARENT(ret);
	}

	return ret;
}

#ifdef _DLIB_RBTREE_SIZE
rbtree_node_t *rb_select(rbtree_node_t *node, uint32_t i)
{
	uint32_t size;

	if (node == NULL) return NULL;
	
	size = RB_SIZE(RB_LEFT(node)) + 1;
	if (i == size) {
		return node;
	} else if (i < size) {
		return rb_select(RB_LEFT(node), i);
	} else {
		return rb_select(RB_RIGHT(node), i - size);
	}
}

uint32_t rb_rank(rbtree_node_t *from, rbtree_node_t *node)
{
	uint32_t size;
	rbtree_node_t *temp;

	if (from == NULL || node == NULL) return 0;
	
	size = RB_SIZE(RB_LEFT(node)) + 1;
	temp = node;

	while (temp != from) {
		if (temp == RB_RIGHT(RB_PARENT(temp))) {
			size += RB_SIZE(RB_LEFT(RB_PARENT(temp))) + 1;
		}
		temp = RB_PARENT(temp);
	}

	return size;
}

uint32_t rb_revrank(rbtree_node_t *from, rbtree_node_t *node)
{
	uint32_t size;
	rbtree_node_t *temp;

	if (from == NULL || node == NULL) return 0;
	
	size = RB_SIZE(RB_LEFT(node)) + 1;
	temp = node;

	while (temp != from) {
		if (temp == RB_LEFT(RB_PARENT(temp))) {
			size += RB_SIZE(RB_RIGHT(RB_PARENT(temp))) + 1;
		}
		temp = RB_PARENT(temp);
	}

	return size;
}
#endif

int rb_insert(rbtree_head_t *head, rbtree_node_t *node,
	      rb_strategy_t strategy)
{
	int flag = 0;
	int cmp = 0;
	rbtree_node_t *cur;
	rbtree_node_t *temp = &rb_leaf;

	if (head == NULL || node == NULL)
		return -1;
	if (RB_COMPARE(head) == NULL || head->key_space == 0)
		return -2;

	/* RB_EXACT handle out for loop */
	if (strategy == RB_EXACT) {
		cur = _rb_find(head, RB_ROOT(head), RB_SEARCH_EQ,
				(void *)((long)node - head->key_space));
		if (cur != NULL) return -10;
	}

	cur = RB_ROOT(head);

	while (cur != &rb_leaf) {
		flag = 0;
		temp = cur;
#ifdef _DLIB_RBTREE_SIZE
		/* maintain the size field */
		++RB_SIZE(cur);
#endif

		cmp = (*RB_COMPARE(head))((void *)((long)node - head->key_space),
					  (void *)((long)cur - head->key_space));
		if (cmp < 0) { /* key[node] < key[cur] */
			flag = 1;
			cur = RB_LEFT(cur);
		} else if (cmp == 0) { /* key[node] == key[cur] */
			cur = RB_RIGHT(cur);
		} else { /* key[node] > key[cur] */
			cur = RB_RIGHT(cur);
		}
	} /* end while */

	INIT_RB_NODE(node, temp, RB_RED);

	if (temp == &rb_leaf) { /* root == NULL */
		RB_ROOT(head) = node;
	} else {
		if (flag == 1) {
			RB_LEFT(temp) = node;
		} else {
			RB_RIGHT(temp) = node;
		}
	}

	_rb_insert_fixup(head, node);

	return 0;
}

rbtree_node_t *rb_delete(rbtree_head_t *head, rbtree_node_t *node)
{
	rbtree_node_t *ret;
	rbtree_node_t *temp;
	rb_color_t ret_color;

	if (head == NULL || node == NULL)
		return NULL;

	if (RB_LEFT(node) == &rb_leaf || RB_RIGHT(node) == &rb_leaf) {
		ret = node;
	} else {
		ret = rb_successor(node);
	}

#ifdef _DLIB_RBTREE_SIZE
	/* maintain the size field */
	rbtree_node_t *cur;
	cur = ret;
	while (cur != RB_ROOT(head)) {
		cur = RB_PARENT(cur);
		--RB_SIZE(cur);
	}
#endif

	if (RB_LEFT(ret) != &rb_leaf) {
		temp = RB_LEFT(ret);
	} else {
		temp = RB_RIGHT(ret);
	}

	RB_PARENT(temp) = RB_PARENT(ret);

	if (RB_PARENT(ret) == &rb_leaf) {
		RB_ROOT(head) = temp;
	} else {
		if (ret == RB_LEFT(RB_PARENT(ret))) {
			RB_LEFT(RB_PARENT(ret)) = temp;
		} else {
			RB_RIGHT(RB_PARENT(ret)) = temp;
		}
	}

	ret_color = RB_COLOR(ret);

	if (ret != node) {
		/**
		 * exchange the pointer or exchange the 
		 * key-value of ret and node(by Spark)
		 */
		RB_COLOR(ret) = RB_COLOR(node);
#ifdef _DLIB_RBTREE_SIZE
		RB_SIZE(ret) = RB_SIZE(node);
#endif

		RB_LEFT(ret) = RB_LEFT(node);
		if (RB_PARENT(RB_LEFT(node)) == node) {
			RB_PARENT(RB_LEFT(node)) = ret;
		}

		RB_RIGHT(ret) = RB_RIGHT(node);
		if (RB_PARENT(RB_RIGHT(node)) == node) {
			RB_PARENT(RB_RIGHT(node)) = ret;
		}

		RB_PARENT(ret) = RB_PARENT(node);
		if (RB_PARENT(node) == &rb_leaf) {
			RB_ROOT(head) = ret;
		}
		if (RB_LEFT(RB_PARENT(node)) == node) {
			RB_LEFT(RB_PARENT(node)) = ret;
		} else {
			RB_RIGHT(RB_PARENT(node)) = ret;
		}
	}

	if (ret_color == RB_BLACK) {
		_rb_delete_fixup(head, temp);
	}

	return node;
}

rbtree_node_t *rb_find(rbtree_head_t *head, rbtree_node_t *node,
		rb_search_t cmd, void *key)
{
	rbtree_node_t *cur;

	if (head == NULL || key == NULL)
		return NULL;

	if (node != NULL && node != &rb_leaf) {
		cur = node;
	} else if (!RB_EMPTY(head)) {
		cur = RB_ROOT(head);
	} else {
		return NULL;
	}

	return _rb_find(head, cur, cmd, key);
}

int rb_inorder(rbtree_head_t *head, rb_walker_fn walker, void *arg)
{
	rbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = RB_ROOT(head);

	_rb_inorder(cur, walker, arg);

	return 0;
}

int rb_postorder(rbtree_head_t *head, rb_walker_fn walker, void *arg)
{
	rbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = RB_ROOT(head);

	_rb_postorder(cur, walker, arg);

	return 0;
}

int rb_preorder(rbtree_head_t *head, rb_walker_fn walker, void *arg)
{
	rbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = RB_ROOT(head);

	_rb_preorder(cur, walker, arg);

	return 0;
}
/* rb-tree OVER */
#endif


#ifndef _DLIB_NO_SPLAYTREE
/**
 * Splay tree model
 * a binary search tree
 * top-down splay implemetation
 */
static inline sptree_node_t *_splay(sptree_head_t *head, sptree_node_t *cur, void *key);
static void _sp_inorder(sptree_node_t *node, sp_walker_fn walker, void *arg);
static void _sp_postorder(sptree_node_t *node, sp_walker_fn walker, void *arg);
static void _sp_preorder(sptree_node_t *node, sp_walker_fn walker, void *arg);

static inline sptree_node_t *_splay(sptree_head_t *head, sptree_node_t *cur, void *key)
{
	static sptree_node_t header;
	sptree_node_t *left_max = &header;
	sptree_node_t *right_min = &header;
	sptree_node_t *temp;
	int cmp = 0;

	if (cur == NULL) cur = SP_ROOT(head);
	if (key == NULL || cur == sp_leaf) return sp_leaf;

	header.left = header.right = sp_leaf;

	cmp = (*SP_COMPARE(head))((void *)((long)cur - head->key_space), key);
	while (cmp != 0) {
		if (cmp > 0) { /* left tree, rotate right */
			if (SP_LEFT(cur) == sp_leaf) break;
			cmp = (*SP_COMPARE(head))
				((void *)((long)(SP_LEFT(cur)) - head->key_space), key);
			if (cmp > 0) {
				temp = SP_LEFT(cur);
				SP_LEFT(cur) = SP_RIGHT(temp);
				SP_RIGHT(temp) = cur;
				cur = temp;
				if (SP_LEFT(cur) == sp_leaf) break;
			}
			/* link right */
			SP_LEFT(right_min) = cur;
			right_min = cur;
			cur = SP_LEFT(cur);
		} else { /* right tree, rotate left */
			if (SP_RIGHT(cur) == sp_leaf) break;
			cmp = (*SP_COMPARE(head))
				((void *)((long)(SP_RIGHT(cur)) - head->key_space), key);
			if (cmp < 0) {
				temp = SP_RIGHT(cur);
				SP_RIGHT(cur) = SP_LEFT(temp);
				SP_LEFT(temp) = cur;
				cur = temp;
				if (SP_RIGHT(cur) == sp_leaf) break;
			}
			/* link left */
			SP_RIGHT(left_max) = cur;
			left_max = cur;
			cur = SP_RIGHT(cur);
		}
		cmp = (*SP_COMPARE(head))((void *)((long)cur - head->key_space), key);
	}

	/* assemble */
	SP_RIGHT(left_max) = SP_LEFT(cur);
	SP_LEFT(right_min) = SP_RIGHT(cur);
	SP_LEFT(cur) = header.right;
	SP_RIGHT(cur) = header.left;

	return cur;
}

static void _sp_inorder(sptree_node_t *node, sp_walker_fn walker, void *arg)
{
	if (node != sp_leaf) {
		_sp_inorder(SP_LEFT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_sp_inorder(SP_RIGHT(node), walker, arg);
	}

	return;
}

static void _sp_postorder(sptree_node_t *node, sp_walker_fn walker, void *arg)
{
	if (node != sp_leaf) {
		_sp_postorder(SP_LEFT(node), walker, arg);
		_sp_postorder(SP_RIGHT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
	}

	return;
}

static void _sp_preorder(sptree_node_t *node, sp_walker_fn walker, void *arg)
{
	if (node != sp_leaf) {
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_sp_preorder(SP_LEFT(node), walker, arg);
		_sp_preorder(SP_RIGHT(node), walker, arg);
	}

	return;
}

int sp_init(sptree_head_t *head, sp_compare_fn compare_fn,
		long key_space, long value_space)
{
	if (head == NULL || compare_fn == NULL || key_space == 0)
		return -1;

	INIT_SP_HEAD(head, compare_fn, key_space, value_space);

	return 0;
}

void sp_exit(sptree_head_t *head, sp_walker_fn sp_free_node, void *arg)
{
	if (head == NULL) return;

	_sp_postorder(SP_ROOT(head), sp_free_node, arg);

	return;
}

sptree_node_t *sp_minimum(sptree_node_t *node)
{
	sptree_node_t *ret = NULL;

	if (node == NULL) return NULL;

	ret = node;
	while (SP_LEFT(ret) != sp_leaf) {
		ret = SP_LEFT(ret);
	}

	return ret;
}

sptree_node_t *sp_maximum(sptree_node_t *node)
{
	sptree_node_t *ret = NULL;

	if (node == NULL) return ret;

	ret = node;
	while (SP_RIGHT(ret) != sp_leaf) {
		ret = SP_RIGHT(ret);
	}

	return ret;
}

int sp_insert(sptree_head_t *head, sptree_node_t *node, sp_strategy_t strategy)
{
	sptree_node_t *cur;
	int cmp = 0;

	if (head == NULL || node == NULL)
		return -1;
	if (SP_COMPARE(head) == NULL || head->key_space == 0)
		return -2;

	if (SP_EMPTY(head)) {
		SP_SET(node, sp_leaf, sp_leaf);

#ifdef _DEBUG
		SP_COUNT(head) = 1;
#endif
		SP_ROOT(head) = node;

		return 0;
	}

	cur = _splay(head, SP_ROOT(head), (void *)((long)node - head->key_space));
	cmp = (*SP_COMPARE(head))((void *)((long)cur - head->key_space),
				  (void *)((long)node - head->key_space));
	if (cmp > 0) {
		SP_LEFT(node) = SP_LEFT(cur);
		SP_RIGHT(node) = cur;
		SP_LEFT(cur) = sp_leaf;
	} else if (cmp < 0) {
		SP_RIGHT(node) = SP_RIGHT(cur);
		SP_LEFT(node) = cur;
		SP_RIGHT(cur) = sp_leaf;
	} else {
		if (strategy == SP_EXACT) {
			return -10;
		} else {
			SP_RIGHT(node) = SP_RIGHT(cur);
			SP_LEFT(node) = cur;
			SP_RIGHT(cur) = sp_leaf;
		}
	}
	
	SP_ROOT(head) = node;
#ifdef _DEBUG
	++SP_COUNT(head);
#endif
	return 0;
}

sptree_node_t *sp_delete(sptree_head_t *head, sptree_node_t *node)
{
	sptree_node_t *cur;
	sptree_node_t *root;
	int cmp = 0;

	if (head == NULL || node == NULL)
		return NULL;
	if (SP_COMPARE(head) == NULL || head->key_space == 0)
		return NULL;
	
	cur = _splay(head, SP_ROOT(head), (void *)((long)node - head->key_space));
	cmp = (*SP_COMPARE(head))((void *)((long)cur - head->key_space),
				  (void *)((long)node - head->key_space));
	if (cmp == 0) {
		if (SP_LEFT(cur) == sp_leaf) {
			root = SP_RIGHT(cur);
		} else {
			root = _splay(head, SP_LEFT(cur),
				      (void *)((long)node - head->key_space));
			SP_RIGHT(root) = SP_RIGHT(cur);
		}

		SP_ROOT(head) = root;
#ifdef _DEBUG
		--SP_COUNT(head);
#endif
		return node;
	} else {
		return NULL;
	}
}

sptree_node_t *sp_find(sptree_head_t *head, sptree_node_t *node, void *key)
{
	sptree_node_t *cur = NULL;
	int cmp = 0;

	if (head == NULL || key == NULL)
		return NULL;
	if (SP_COMPARE(head) == NULL || head->key_space == 0)
		return NULL;
	
	if (node != sp_leaf) cur = node;

	cur = _splay(head, cur, key);
	SP_ROOT(head) = cur;

	cmp = (*SP_COMPARE(head))((void *)((long)cur - head->key_space), key);
	if (cmp == 0) {
		return cur;
	} else {
		return NULL;
	}
}

int sp_inorder(sptree_head_t *head, sp_walker_fn walker, void *arg)
{
	sptree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SP_ROOT(head);

	_sp_inorder(cur, walker, arg);

	return 0;
}

int sp_postorder(sptree_head_t *head, sp_walker_fn walker, void *arg)
{
	sptree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SP_ROOT(head);

	_sp_postorder(cur, walker, arg);

	return 0;
}

int sp_preorder(sptree_head_t *head, sp_walker_fn walker, void *arg)
{
	sptree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SP_ROOT(head);

	_sp_preorder(cur, walker, arg);

	return 0;
}
/** splay-tree OVER */
#endif


#ifndef _DLIB_NO_SBTREE
/**
 * SBT tree model
 * a quickest size-maintained BST
 */
sbtree_node_t sb_leaf = {
	&sb_leaf,
	&sb_leaf,
	&sb_leaf,
	0,
};

static inline void _sb_rotate_left(sbtree_head_t *head, sbtree_node_t *node);
static inline void _sb_rotate_right(sbtree_head_t *head, sbtree_node_t *node);
static inline void _sb_maintain(sbtree_head_t *head, sbtree_node_t *node, int flag);
static sbtree_node_t *_sb_find(sbtree_head_t *head, sbtree_node_t *node, void *key);
static int _sb_insert(sbtree_head_t *head, sbtree_node_t *cur, sbtree_node_t *node);
static void _sb_inorder(sbtree_node_t *node, sb_walker_fn walker, void *arg);
static void _sb_postorder(sbtree_node_t *node, sb_walker_fn walker, void *arg);
static void _sb_preorder(sbtree_node_t *node, sb_walker_fn walker, void *arg);

static inline void _sb_rotate_left(sbtree_head_t *head, sbtree_node_t *node)
{
	sbtree_node_t *temp;

	temp = SB_RIGHT(node);
	SB_RIGHT(node) = SB_LEFT(temp);
	if (SB_LEFT(temp) != &sb_leaf) {
		SB_PARENT(SB_LEFT(temp)) = node;
	}

	SB_PARENT(temp) = SB_PARENT(node);

	if (SB_PARENT(node) == &sb_leaf) {
		SB_ROOT(head) = temp;
	} else {
		if (node == SB_LEFT(SB_PARENT(node))) {
			SB_LEFT(SB_PARENT(node)) = temp;
		} else {
			SB_RIGHT(SB_PARENT(node)) = temp;
		}
	}

	SB_LEFT(temp) = node;
	SB_PARENT(node) = temp;
	SB_SIZE(temp) = SB_SIZE(node);
	SB_SIZE(node) = SB_SIZE(SB_LEFT(node)) + SB_SIZE(SB_RIGHT(node)) + 1;

	return;
}

static inline void _sb_rotate_right(sbtree_head_t *head, sbtree_node_t *node)
{
	sbtree_node_t *temp;

	temp = SB_LEFT(node);
	SB_LEFT(node) = SB_RIGHT(temp);
	if (SB_RIGHT(temp) != &sb_leaf) {
		SB_PARENT(SB_RIGHT(temp)) = node;
	}

	SB_PARENT(temp) = SB_PARENT(node);

	if (SB_PARENT(node) == &sb_leaf) {
		SB_ROOT(head) = temp;
	} else {
		if (node == SB_RIGHT(SB_PARENT(node))) {
			SB_RIGHT(SB_PARENT(node)) = temp;
		} else {
			SB_LEFT(SB_PARENT(node)) = temp;
		}
	}

	SB_RIGHT(temp) = node;
	SB_PARENT(node) = temp;
	SB_SIZE(temp) = SB_SIZE(node);
	SB_SIZE(node) = SB_SIZE(SB_LEFT(node)) + SB_SIZE(SB_RIGHT(node)) + 1;

	return;
}

static inline void _sb_maintain(sbtree_head_t *head, sbtree_node_t *node, int flag)
{
	if (flag <= 0) { /* left */
		if (SB_SIZE(SB_LEFT(SB_LEFT(node))) > SB_SIZE(SB_RIGHT(node))) { /* case 1 */
			_sb_rotate_right(head, node);
		} else if (SB_SIZE(SB_RIGHT(SB_LEFT(node))) > SB_SIZE(SB_RIGHT(node))) { /* case 2 */
			_sb_rotate_left(head, SB_LEFT(node));
			_sb_rotate_right(head, node);
		} else {
			return;
		}
	} else { /* right */
		if (SB_SIZE(SB_RIGHT(SB_RIGHT(node))) > SB_SIZE(SB_LEFT(node))) { /* case 3 */
			_sb_rotate_left(head, node);
		} else if (SB_SIZE(SB_LEFT(SB_RIGHT(node))) > SB_SIZE(SB_LEFT(node))) { /* case 4 */
			_sb_rotate_right(head, SB_RIGHT(node));
			_sb_rotate_left(head, node);
		} else {
			return;
		}
	}
	
	_sb_maintain(head, SB_LEFT(node), 0);
	_sb_maintain(head, SB_RIGHT(node), 1);
	_sb_maintain(head, node, 0);
	_sb_maintain(head, node, 1);

	return;
}

static sbtree_node_t *_sb_find(sbtree_head_t *head, sbtree_node_t *node, void *key)
{
	int cmp;
	sbtree_node_t *ret = NULL;

	cmp = (*SB_COMPARE(head))((void *)((long)node - head->key_space), key);
	while (node != &sb_leaf && cmp != 0) {
		if (cmp < 0) {
			node = SB_RIGHT(node);
		} else {
			node = SB_LEFT(node);
		}
		if (node != &sb_leaf) {
			cmp = (*SB_COMPARE(head))
				((void *)((long)node - head-> key_space), key);
		}
	}

	if (node != &sb_leaf)
		ret = node;

	return ret;
}

static int _sb_insert(sbtree_head_t *head, sbtree_node_t *cur, sbtree_node_t *node)
{
	int ret = 0;
	int flag;
	int cmp = 0;

	++SB_SIZE(cur);
	cmp = (*SB_COMPARE(head))((void *)((long)node - head->key_space),
				  (void *)((long)cur - head->key_space));
	if (cmp < 0) {
		if (SB_LEFT(cur) == &sb_leaf) {
			SB_LEFT(cur) = node;
			SB_PARENT(node) = cur;
			return 0;
		} else {
			flag = 0;
			ret = _sb_insert(head, SB_LEFT(cur), node);
		}
	} else {
		if (SB_RIGHT(cur) == &sb_leaf) {
			SB_RIGHT(cur) = node;
			SB_PARENT(node) = cur;
			return 0;
		} else {
			flag = 1;
			ret = _sb_insert(head, SB_RIGHT(cur), node);
		}
	}

	_sb_maintain(head, cur, flag);

	return ret;
}

static void _sb_inorder(sbtree_node_t *node, sb_walker_fn walker, void *arg)
{
	if (node != &sb_leaf) {
		_sb_inorder(SB_LEFT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_sb_inorder(SB_RIGHT(node), walker, arg);
	}

	return;
}

static void _sb_postorder(sbtree_node_t *node, sb_walker_fn walker, void *arg)
{
	if (node != &sb_leaf) {
		_sb_postorder(SB_LEFT(node), walker, arg);
		_sb_postorder(SB_RIGHT(node), walker, arg);
		if (walker != NULL) {
			(*walker) (node, arg);
		}
	}

	return;
}

static void _sb_preorder(sbtree_node_t *node, sb_walker_fn walker, void *arg)
{
	if (node != &sb_leaf) {
		if (walker != NULL) {
			(*walker) (node, arg);
		}
		_sb_preorder(SB_LEFT(node), walker, arg);
		_sb_preorder(SB_RIGHT(node), walker, arg);
	}

	return;
}

int sb_init(sbtree_head_t *head, sb_compare_fn compare_fn,
		long key_space, long value_space)
{
	if (head == NULL || compare_fn == NULL || key_space == 0)
		return -1;

	INIT_SB_HEAD(head, compare_fn, key_space, value_space);

	return 0;
}

void sb_exit(sbtree_head_t *head, sb_walker_fn sb_free_node, void *arg)
{
	if (head == NULL) return;

	_sb_postorder(SB_ROOT(head), sb_free_node, arg);

	return;
}

sbtree_node_t *sb_minimum(sbtree_node_t *node)
{
	sbtree_node_t *ret = NULL;

	if (node == NULL)
		return NULL;

	ret = node;

	while (SB_LEFT(ret) != &sb_leaf) {
		ret = SB_LEFT(ret);
	}

	return ret;
}

sbtree_node_t *sb_maximum(sbtree_node_t *node)
{
	sbtree_node_t *ret = NULL;

	if (node == NULL)
		return ret;

	ret = node;

	while (SB_RIGHT(ret) != &sb_leaf) {
		ret = SB_RIGHT(ret);
	}

	return ret;
}

sbtree_node_t *sb_predecessor(sbtree_node_t *node)
{
	sbtree_node_t *ret;
	sbtree_node_t *temp;

	if (node == NULL) return NULL;

	ret = SB_LEFT(node);

	if (ret != &sb_leaf) {
		return sb_maximum(ret);
	}

	ret = SB_PARENT(node);
	temp = node;
	while (ret != &sb_leaf && temp == SB_LEFT(ret)) {
		temp = ret;
		ret = SB_PARENT(ret);
	}

	return ret;
}

sbtree_node_t *sb_successor(sbtree_node_t *node)
{
	sbtree_node_t *ret;
	sbtree_node_t *temp;

	if (node == NULL) return NULL;

	ret = SB_RIGHT(node);

	if (ret != &sb_leaf) {
		return sb_minimum(ret);
	}

	ret = SB_PARENT(node);
	temp = node;
	while (ret != &sb_leaf && temp == SB_RIGHT(ret)) {
		temp = ret;
		ret = SB_PARENT(ret);
	}

	return ret;
}

/* select and rank/rankrev */
sbtree_node_t *sb_select(sbtree_node_t *node, uint32_t i)
{
	uint32_t size = 0;

	if (node == NULL || node == &sb_leaf) return NULL;
	
	size = SB_SIZE(SB_LEFT(node)) + 1;
	if (i == size) {
		return node;
	} else if (i < size) {
		return sb_select(SB_LEFT(node), i);
	} else {
		return sb_select(SB_RIGHT(node), i - size);
	}
}

uint32_t sb_rank(sbtree_node_t *from, sbtree_node_t *node)
{
	uint32_t size = 0;
	sbtree_node_t *temp;

	if (from == NULL || node == NULL) return 0;
	
	size = SB_SIZE(SB_LEFT(node)) + 1;
	temp = node;

	while (temp != from) {
		if (temp == SB_RIGHT(SB_PARENT(temp))) {
			size += SB_SIZE(SB_LEFT(SB_PARENT(temp))) + 1;
		}
		temp = SB_PARENT(temp);
	}

	return size;
}

uint32_t sb_revrank(sbtree_node_t *from, sbtree_node_t *node)
{
	uint32_t size = 0;
	sbtree_node_t *temp;

	if (from == NULL || node == NULL) return 0;
	
	size = SB_SIZE(SB_LEFT(node)) + 1;
	temp = node;

	while (temp != from) {
		if (temp == SB_LEFT(SB_PARENT(temp))) {
			size += SB_SIZE(SB_RIGHT(SB_PARENT(temp))) + 1;
		}
		temp = SB_PARENT(temp);
	}

	return size;
}

int sb_insert(sbtree_head_t *head, sbtree_node_t *node,
	      sb_strategy_t strategy)
{
	sbtree_node_t *cur;

	if (head == NULL || node == NULL)
		return -1;
	if (SB_COMPARE(head) == NULL || head->key_space == 0)
		return -2;

	/* SB_EXACT handle out for loop */
	if (strategy == SB_EXACT) {
		cur = _sb_find(head, SB_ROOT(head),
			       (void *)((long)node - head->key_space));
		if (cur != NULL) return -10;
	}

	INIT_SB_NODE(node);

	if (SB_EMPTY(head)) {
		SB_ROOT(head) = node;
#ifdef _DEBUG
		SB_COUNT(head) = 1;
#endif
		return 0;
	} else {
#ifdef _DEBUG
		SB_COUNT(head)++;
#endif
		return _sb_insert(head, SB_ROOT(head), node);
	}
}

sbtree_node_t *sb_delete(sbtree_head_t *head, sbtree_node_t *node)
{
	sbtree_node_t *ret;
	sbtree_node_t *temp;
	sbtree_node_t *cur;

	if (head == NULL || node == NULL) return NULL;

	if (SB_LEFT(node) == &sb_leaf || SB_RIGHT(node) == &sb_leaf) {
		ret = node;
	} else {
		ret = sb_successor(node);
	}

	/* maintain the size field */
	cur = ret;
	while (cur != SB_ROOT(head)) {
		cur = SB_PARENT(cur);
		--SB_SIZE(cur);
	}

	if (SB_LEFT(ret) != &sb_leaf) {
		temp = SB_LEFT(ret);
	} else {
		temp = SB_RIGHT(ret);
	}

	SB_PARENT(temp) = SB_PARENT(ret);

	if (SB_PARENT(ret) == &sb_leaf) {
		SB_ROOT(head) = temp;
	} else {
		if (ret == SB_LEFT(SB_PARENT(ret))) {
			SB_LEFT(SB_PARENT(ret)) = temp;
		} else {
			SB_RIGHT(SB_PARENT(ret)) = temp;
		}
	}

	if (ret != node) {
	/* exchange the pointer or
	 * exchange the key-value of ret and node
	 */
		SB_SIZE(ret) = SB_SIZE(node);

		SB_LEFT(ret) = SB_LEFT(node);
		if (SB_PARENT(SB_LEFT(node)) == node) {
			SB_PARENT(SB_LEFT(node)) = ret;
		}

		SB_RIGHT(ret) = SB_RIGHT(node);
		if (SB_PARENT(SB_RIGHT(node)) == node) {
			SB_PARENT(SB_RIGHT(node)) = ret;
		}

		SB_PARENT(ret) = SB_PARENT(node);
		if (SB_PARENT(node) == &sb_leaf) {
			SB_ROOT(head) = ret;
		}
		if (SB_LEFT(SB_PARENT(node)) == node) {
			SB_LEFT(SB_PARENT(node)) = ret;
		} else {
			SB_RIGHT(SB_PARENT(node)) = ret;
		}
	}

#ifdef _DEBUG
	--SB_COUNT(head);
#endif
	return node;
}

sbtree_node_t *sb_find(sbtree_head_t *head, sbtree_node_t *node, void *key)
{
	sbtree_node_t *cur;

	if (head == NULL || key == NULL)
		return NULL;

	if (node != NULL) {
		cur = node;
	} else {
		cur = SB_ROOT(head);
	}

	return _sb_find(head, cur, key);
}

int sb_inorder(sbtree_head_t *head, sb_walker_fn walker, void *arg)
{
	sbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SB_ROOT(head);

	_sb_inorder(cur, walker, arg);

	return 0;
}

int sb_postorder(sbtree_head_t *head, sb_walker_fn walker, void *arg)
{
	sbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SB_ROOT(head);

	_sb_postorder(cur, walker, arg);

	return 0;
}

int sb_preorder(sbtree_head_t *head, sb_walker_fn walker, void *arg)
{
	sbtree_node_t *cur;

	if (head == NULL)
		return -1;

	cur = SB_ROOT(head);

	_sb_preorder(cur, walker, arg);

	return 0;
}
/* end size balance tree */
#endif


/* Treap model
 *
 */



/* trie tree model
 *
 */



/* merkle tree model
 *
 */



/* B+ tree model
 *
 */



/* K-D tree
 *
 */



